
/*
 * re_*comp and friends - 编译正则表达式
 * This file #includes several others (see the bottom).
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 *
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them.
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * src/backend/regex/regcomp.c
 *
 */

#include "regex/regguts.h"

/*
 * 向前声明，在这里前向定义数据类型等
 */
/* === regcomp.c === */
static void moresubs(struct vars *, int);
static int	freev(struct vars *, int);
static void makesearch(struct vars *, struct nfa *);
static struct subre *parse(struct vars *, int, int, struct state *, struct state *);
static struct subre *parsebranch(struct vars *, int, int, struct state *, struct state *, int);
static struct subre *parseqatom(struct vars *, int, int, struct state *, struct state *, struct subre *);
static void nonword(struct vars *, int, struct state *, struct state *);
static void word(struct vars *, int, struct state *, struct state *);
static void charclass(struct vars *, enum char_classes,
					  struct state *, struct state *);
static void charclasscomplement(struct vars *, enum char_classes,
								struct state *, struct state *);
static int	scannum(struct vars *);
static void repeat(struct vars *, struct state *, struct state *, int, int);
static void bracket(struct vars *, struct state *, struct state *);
static void cbracket(struct vars *, struct state *, struct state *);
static void brackpart(struct vars *, struct state *, struct state *, bool *);
static const chr *scanplain(struct vars *);
static void onechr(struct vars *, chr, struct state *, struct state *);
static void optimizebracket(struct vars *, struct state *, struct state *);
static void wordchrs(struct vars *);
static void processlacon(struct vars *, struct state *, struct state *, int,
						 struct state *, struct state *);
static struct subre *subre(struct vars *, int, int, struct state *, struct state *);
static void freesubre(struct vars *, struct subre *);
static void freesubreandsiblings(struct vars *, struct subre *);
static void freesrnode(struct vars *, struct subre *);
static void removecaptures(struct vars *, struct subre *);
static int	numst(struct subre *, int);
static void markst(struct subre *);
static void cleanst(struct vars *);
static long nfatree(struct vars *, struct subre *, FILE *);
static long nfanode(struct vars *, struct subre *, int, FILE *);
static int	newlacon(struct vars *, struct state *, struct state *, int);
static void freelacons(struct subre *, int);
static void rfree(regex_t *);
static int	rcancelrequested(void);
static int	rstacktoodeep(void);

#ifdef REG_DEBUG
static void dump(regex_t *, FILE *);
static void dumpst(struct subre *, FILE *, int);
static void stdump(struct subre *, FILE *, int);
static const char *stid(struct subre *, char *, size_t);
#endif
/* === regc_lex.c === */
static void lexstart(struct vars *);
static void prefixes(struct vars *);
static int	next(struct vars *);
static int	lexescape(struct vars *);
static chr	lexdigits(struct vars *, int, int, int);
static int	brenext(struct vars *, chr);
static void skip(struct vars *);
static chr	newline(void);
static chr	chrnamed(struct vars *, const chr *, const chr *, chr);

/* === regc_color.c === */
static void initcm(struct vars *, struct colormap *);
static void freecm(struct colormap *);
static color maxcolor(struct colormap *);
static color newcolor(struct colormap *);
static void freecolor(struct colormap *, color);
static color pseudocolor(struct colormap *);
static color subcolor(struct colormap *, chr);
static color subcolorhi(struct colormap *, color *);
static color newsub(struct colormap *, color);
static int	newhicolorrow(struct colormap *, int);
static void newhicolorcols(struct colormap *);
static void subcolorcvec(struct vars *, struct cvec *, struct state *, struct state *);
static void subcoloronechr(struct vars *, chr, struct state *, struct state *, color *);
static void subcoloronerange(struct vars *, chr, chr, struct state *, struct state *, color *);
static void subcoloronerow(struct vars *, int, struct state *, struct state *, color *);
static void okcolors(struct nfa *, struct colormap *);
static void colorchain(struct colormap *, struct arc *);
static void uncolorchain(struct colormap *, struct arc *);
static void rainbow(struct nfa *, struct colormap *, int, color, struct state *, struct state *);
static void colorcomplement(struct nfa *, struct colormap *, int, struct state *, struct state *, struct state *);

#ifdef REG_DEBUG
static void dumpcolors(struct colormap *, FILE *);
static void dumpchr(chr, FILE *);
#endif
/* === regc_nfa.c === */
static struct nfa *newnfa(struct vars *, struct colormap *, struct nfa *);
static void freenfa(struct nfa *);
static struct state *newstate(struct nfa *);
static struct state *newfstate(struct nfa *, int fc_flag);
static void dropstate(struct nfa *, struct state *);
static void freestate(struct nfa *, struct state *);
static void newarc(struct nfa *, int, color, struct state *, struct state *);
static void createarc(struct nfa *, int, color, struct state *, struct state *);
static struct arc *allocarc(struct nfa *);
static void freearc(struct nfa *, struct arc *);
static void changearcsource(struct arc *, struct state *);
static void changearctarget(struct arc *, struct state *);
static int	hasnonemptyout(struct state *);
static struct arc *findarc(struct state *, int, color);
static void cparc(struct nfa *, struct arc *, struct state *, struct state *);
static void sortins(struct nfa *, struct state *);
static int	sortins_cmp(const void *, const void *);
static void sortouts(struct nfa *, struct state *);
static int	sortouts_cmp(const void *, const void *);
static void moveins(struct nfa *, struct state *, struct state *);
static void copyins(struct nfa *, struct state *, struct state *);
static void mergeins(struct nfa *, struct state *, struct arc **, int);
static void moveouts(struct nfa *, struct state *, struct state *);
static void copyouts(struct nfa *, struct state *, struct state *);
static void cloneouts(struct nfa *, struct state *, struct state *, struct state *, int);
static void delsub(struct nfa *, struct state *, struct state *);
static void deltraverse(struct nfa *, struct state *, struct state *);
static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *);
static void duptraverse(struct nfa *, struct state *, struct state *);
static void removeconstraints(struct nfa *, struct state *, struct state *);
static void removetraverse(struct nfa *, struct state *);
static void cleartraverse(struct nfa *, struct state *);
static struct state *single_color_transition(struct state *, struct state *);
static void specialcolors(struct nfa *);
static long optimize(struct nfa *, FILE *);
static void pullback(struct nfa *, FILE *);
static int	pull(struct nfa *, struct arc *, struct state **);
static void pushfwd(struct nfa *, FILE *);
static int	push(struct nfa *, struct arc *, struct state **);

#define INCOMPATIBLE	1		/* 销毁弧 */
#define SATISFIED	2			/* 约束满足 */
#define COMPATIBLE	3			/* 兼容但尚未满足 */
#define REPLACEARC	4			/* 用约束颜色替换弧的颜色 */
static int	combine(struct nfa *fc_nfa, struct arc *fc_con, struct arc *fc_a);
static void fixempties(struct nfa *, FILE *);
static struct state *emptyreachable(struct nfa *, struct state *,
									struct state *, struct arc **);
static int	isconstraintarc(struct arc *);
static int	hasconstraintout(struct state *);
static void fixconstraintloops(struct nfa *, FILE *);
static int	findconstraintloop(struct nfa *, struct state *);
static void breakconstraintloop(struct nfa *, struct state *);
static void clonesuccessorstates(struct nfa *, struct state *, struct state *,
								 struct state *, struct arc *,
								 char *, char *, int);
static void removecantmatch(struct nfa *);
static void cleanup(struct nfa *);
static void markreachable(struct nfa *, struct state *, struct state *, struct state *);
static void markcanreach(struct nfa *, struct state *, struct state *, struct state *);
static long analyze(struct nfa *);
static void checkmatchall(struct nfa *);
static bool checkmatchall_recurse(struct nfa *, struct state *, bool **);
static bool check_out_colors_match(struct state *, color, color);
static bool check_in_colors_match(struct state *, color, color);
static void compact(struct nfa *, struct cnfa *);
static void carcsort(struct carc *, size_t);
static int	carc_cmp(const void *, const void *);
static void freecnfa(struct cnfa *);
static void dumpnfa(struct nfa *, FILE *);

#ifdef REG_DEBUG
static void dumpstate(struct state *, FILE *);
static void dumparcs(struct state *, FILE *);
static void dumparc(struct arc *, struct state *, FILE *);
static void dumpcnfa(struct cnfa *, FILE *);
static void dumpcstate(int, struct cnfa *, FILE *);
#endif
/* === regc_cvec.c === */
static struct cvec *newcvec(int, int);
static struct cvec *clearcvec(struct cvec *);
static void addchr(struct cvec *, chr);
static void addrange(struct cvec *, chr, chr);
static struct cvec *getcvec(struct vars *, int, int);
static void freecvec(struct cvec *);

/* === regc_pg_locale.c === */
static int	pg_wc_isdigit(pg_wchar fc_c);
static int	pg_wc_isalpha(pg_wchar fc_c);
static int	pg_wc_isalnum(pg_wchar fc_c);
static int	pg_wc_isword(pg_wchar fc_c);
static int	pg_wc_isupper(pg_wchar fc_c);
static int	pg_wc_islower(pg_wchar fc_c);
static int	pg_wc_isgraph(pg_wchar fc_c);
static int	pg_wc_isprint(pg_wchar fc_c);
static int	pg_wc_ispunct(pg_wchar fc_c);
static int	pg_wc_isspace(pg_wchar fc_c);
static pg_wchar pg_wc_toupper(pg_wchar fc_c);
static pg_wchar pg_wc_tolower(pg_wchar fc_c);

/* === regc_locale.c === */
static chr	element(struct vars *, const chr *, const chr *);
static struct cvec *range(struct vars *, chr, chr, int);
static int	before(chr, chr);
static struct cvec *eclass(struct vars *, chr, int);
static enum char_classes lookupcclass(struct vars *, const chr *, const chr *);
static struct cvec *cclasscvec(struct vars *, enum char_classes, int);
static int	cclass_column_index(struct colormap *, chr);
static struct cvec *allcases(struct vars *, chr);
static int	cmp(const chr *, const chr *, size_t);
static int	casecmp(const chr *, const chr *, size_t);


/* 内部变量，捆绑以便于传递 */
struct vars
{
	regex_t    *re;
	const chr  *now;			/* 扫描指针进入字符串 */
	const chr  *stop;			/* 字符串的结束 */
	int			err;			/* 错误代码（如果没有，则为0） */
	int			cflags;			/* 编译标志的副本 */
	int			lasttype;		/* 上一个标记的类型 */
	int			nexttype;		/* 下一个标记的类型 */
	chr			nextvalue;		/* 下一个标记的值（如果有） */
	int			lexcon;			/* 词法上下文类型（见 regc_lex.c） */
	int			nsubexp;		/* 子表达式计数 */
	struct subre **subs;		/* subRE 指针向量 */
	size_t		nsubs;			/* 向量的长度 */
	struct subre *sub10[10];	/* 初始向量，对大多数情况足够 */
	struct nfa *nfa;			/* the NFA */
	struct colormap *cm;		/* 字符颜色映射 */
	color		nlcolor;		/* 换行符的颜色 */
	struct state *wordchrs;		/* 状态在 nfa 中持有单词字符的出边 */
	struct subre *tree;			/* 子表达式树 */
	struct subre *treechain;	/* 所有树节点已分配 */
	struct subre *treefree;		/* 任何空闲的树节点 */
	int			ntree;			/* 树节点的数量，加一 */
	struct cvec *cv;			/* 接口 cvec */
	struct cvec *cv2;			/* 工具 cvec */
	struct subre *lacons;		/* 前瞻约束向量 */
	int			nlacons;		/* lacons[] 的大小；注意只有编号为 1 .. nlacons-1 的槽被使用 */
	size_t		spaceused;		/* 编译时使用的近似空间 */
};

/* 解析宏；大多数人知道 `v` 是结构体变量指针 */
#define NEXT()	(next(v))		/* 向前推进一个令牌 */
#define SEE(t)	(v->nexttype == (t))	/* 下一个令牌是这个吗？ */
#define EAT(t)	(SEE(t) && next(v)) /* 如果下一个是这个，吞下它 */
#define VISERR(vv)	((vv)->err != 0)	/* 我们是否已经看到错误？ */
#define ISERR() VISERR(v)
#define VERR(vv,e)	((vv)->nexttype = EOS, \
					 (vv)->err = ((vv)->err ? (vv)->err : (e)))
#define ERR(e)	VERR(v, e)		/* 记录一个错误 */
#define NOERR() {if (ISERR()) return;}	/* 如果看到错误，则返回 */
#define NOERRN()	{if (ISERR()) return NULL;} /* 没有错误，带返回值 */
#define NOERRZ()	{if (ISERR()) return 0;}	/* 没有错误，带返回值 */
#define INSIST(c, e) do { if (!(c)) ERR(e); } while (0) /* 如果 c 为假则出错 */
#define NOTE(b) (v->re->re_info |= (b)) /* 注意可见条件 */
#define EMPTYARC(x, y)	newarc(v->nfa, EMPTY, 0, x, y)

/* 令牌类型代码，有些也用作 NFA 弧类型 */
#define EMPTY	'n'				/* 没有令牌存在 */
#define EOS 'e'					/* 字符串的结束 */
#define PLAIN	'p'				/* 普通字符 */
#define DIGIT	'd'				/* 数字（在范围内） */
#define BACKREF 'b'				/* 反向引用 */
#define COLLEL	'I'				/* [. 的开始 */
#define ECLASS	'E'				/* [= 的开始 */
#define CCLASS	'C'				/* [: 的开始 */
#define END 'X'					/* [. [= [: 的结束 */
#define CCLASSS	's'				/* 字符类简写转义 */
#define CCLASSC	'c'				/* 补充字符类简写转义 */
#define RANGE	'R'				/* 在[]内可能是范围分隔符。 */
#define LACON	'L'				/* 先行约束子表达式 */
#define AHEAD	'a'				/* 颜色先行弧 */
#define BEHIND	'r'				/* 颜色后行弧 */
#define WBDRY	'w'				/* 单词边界约束 */
#define NWBDRY	'W'				/* 非单词边界约束 */
#define CANTMATCH 'x'			/* 不能匹配任何内容的弧 */
#define SBEGIN	'A'				/* 字符串开始（即使不是行首） */
#define SEND	'Z'				/* 字符串结束（即使不是行尾） */

/* 这是一个着色的弧，因此应该属于颜色链吗？ */
/* 对“co”的测试消除了RAINBOW弧，我们不打算链接它们 */
#define COLORED(a) \
	((a)->co >= 0 && \
	 ((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND))


/* 静态函数列表 */
static const struct fns functions = {
	rfree,						/* regfree内部 */
	rcancelrequested,			/* 检查取消请求 */
	rstacktoodeep				/* 检查栈是否变得危险地深 */
};



/*
 * pg_regcomp - 编译正则表达式
 *
 * 注意：在失败情况下，没有资源被分配，因此不需要将pg_regfree()
 * 应用于re。
 */
int pg_regcomp(regex_t *fc_re,
		   const chr *fc_string,
		   size_t fc_len,
		   int fc_flags,
		   Oid fc_collation)
{
	struct vars fc_var;
	struct vars *v = &fc_var;
	struct guts *fc_g;
	int			fc_i;
	size_t		fc_j;

#ifdef REG_DEBUG
	FILE	   *fc_debug = (fc_flags & REG_PROGRESS) ? stdout : (FILE *) NULL;
#else
	FILE	   *fc_debug = (FILE *) NULL;
#endif

#define  CNOERR()	 { if (ISERR()) return freev(v, v->err); }

	/* 运行检查 */

	if (fc_re == NULL || fc_string == NULL)
		return REG_INVARG;
	if ((fc_flags & REG_QUOTE) &&
		(fc_flags & (REG_ADVANCED | REG_EXPANDED | REG_NEWLINE)))
		return REG_INVARG;
	if (!(fc_flags & REG_EXTENDED) && (fc_flags & REG_ADVF))
		return REG_INVARG;

	/* 初始化区域相关支持 */
	pg_set_regex_collation(fc_collation);

	/* 初始设置（之后可以调用freev()） */
	v->re = fc_re;
	v->now = fc_string;
	v->stop = v->now + fc_len;
	v->err = 0;
	v->cflags = fc_flags;
	v->nsubexp = 0;
	v->subs = v->sub10;
	v->nsubs = 10;
	for (fc_j = 0; fc_j < v->nsubs; fc_j++)
		v->subs[fc_j] = NULL;
	v->nfa = NULL;
	v->cm = NULL;
	v->nlcolor = COLORLESS;
	v->wordchrs = NULL;
	v->tree = NULL;
	v->treechain = NULL;
	v->treefree = NULL;
	v->cv = NULL;
	v->cv2 = NULL;
	v->lacons = NULL;
	v->nlacons = 0;
	v->spaceused = 0;
	fc_re->re_magic = REMAGIC;
	fc_re->re_info = 0;			/* 解析过程中设置的位 */
	fc_re->re_csize = sizeof(chr);
	fc_re->re_collation = fc_collation;
	fc_re->re_guts = NULL;
	fc_re->re_fns = VS(&functions);

	/* 更复杂的设置，动态分配的东西 */
	fc_re->re_guts = VS(MALLOC(sizeof(struct guts)));
	if (fc_re->re_guts == NULL)
		return freev(v, REG_ESPACE);
	fc_g = (struct guts *) fc_re->re_guts;
	fc_g->tree = NULL;
	initcm(v, &fc_g->cmap);
	v->cm = &fc_g->cmap;
	fc_g->lacons = NULL;
	fc_g->nlacons = 0;
	ZAPCNFA(fc_g->search);
	v->nfa = newnfa(v, v->cm, (struct nfa *) NULL);
	CNOERR();
	/* 为getcvec使用设置一个合理大小的瞬态cvec */
	v->cv = newcvec(100, 20);
	if (v->cv == NULL)
		return freev(v, REG_ESPACE);

	/* parsing */
	lexstart(v);				/* 还处理前缀 */
	if ((v->cflags & REG_NLSTOP) || (v->cflags & REG_NLANCH))
	{
		/* 将换行符分配一个唯一颜色 */
		v->nlcolor = subcolor(v->cm, newline());
		okcolors(v->nfa, v->cm);
	}
	CNOERR();
	v->tree = parse(v, EOS, PLAIN, v->nfa->init, v->nfa->final);
	assert(SEE(EOS));			/* 即使发生错误； ISERR() => SEE(EOS) */
	CNOERR();
	assert(v->tree != NULL);

	/* 完成nfa及其子表达式树的设置 */
	specialcolors(v->nfa);
	CNOERR();
#ifdef REG_DEBUG
	if (fc_debug != NULL)
	{
		fprintf(fc_debug, "\n\n\n========= RAW ==========\n");
		dumpnfa(v->nfa, fc_debug);
		dumpst(v->tree, fc_debug, 1);
	}
#endif
	if (v->cflags & REG_NOSUB)
		removecaptures(v, v->tree);
	v->ntree = numst(v->tree, 1);
	markst(v->tree);
	cleanst(v);
#ifdef REG_DEBUG
	if (fc_debug != NULL)
	{
		fprintf(fc_debug, "\n\n\n========= TREE FIXED ==========\n");
		dumpst(v->tree, fc_debug, 1);
	}
#endif

	/* 为树和lacons构建压缩的NFA */
	fc_re->re_info |= nfatree(v, v->tree, fc_debug);
	CNOERR();
	assert(v->nlacons == 0 || v->lacons != NULL);
	for (fc_i = 1; fc_i < v->nlacons; fc_i++)
	{
		struct subre *fc_lasub = &v->lacons[fc_i];

#ifdef REG_DEBUG
		if (fc_debug != NULL)
			fprintf(fc_debug, "\n\n\n========= LA%d ==========\n", fc_i);
#endif

		/* 如果模式是后行LACON，则在模式前添加.* */
		nfanode(v, fc_lasub, !LATYPE_IS_AHEAD(fc_lasub->latype), fc_debug);
	}
	CNOERR();
	if (v->tree->flags & SHORTER)
		NOTE(REG_USHORTEST);

	/* 为树、lacons、快速搜索构建压缩的NFA */
#ifdef REG_DEBUG
	if (fc_debug != NULL)
		fprintf(fc_debug, "\n\n\n========= SEARCH ==========\n");
#endif
	/* 现在可以牺牲主NFA，因此将其用作工作区 */
	(DISCARD) optimize(v->nfa, fc_debug);
	CNOERR();
	makesearch(v, v->nfa);
	CNOERR();
	compact(v->nfa, &fc_g->search);
	CNOERR();

	/* 看起来不错，打包起来 */
	fc_re->re_nsub = v->nsubexp;
	v->re = NULL;				/* freev不再释放re */
	fc_g->magic = GUTSMAGIC;
	fc_g->cflags = v->cflags;
	fc_g->info = fc_re->re_info;
	fc_g->nsub = fc_re->re_nsub;
	fc_g->tree = v->tree;
	v->tree = NULL;
	fc_g->ntree = v->ntree;
	fc_g->compare = (v->cflags & REG_ICASE) ? casecmp : cmp;
	fc_g->lacons = v->lacons;
	v->lacons = NULL;
	fc_g->nlacons = v->nlacons;

#ifdef REG_DEBUG
	if (fc_flags & REG_DUMP)
	{
		dump(fc_re, stdout);
		fflush(stdout);
	}
#endif

	assert(v->err == 0);
	return freev(v, 0);
}

/*
 * moresubs - 扩大subRE向量
 */
static void moresubs(struct vars *v,
		 int fc_wanted)			/* 为这一项留出足够的空间 */
{
	struct subre **fc_p;
	size_t		fc_n;

	assert(fc_wanted > 0 && (size_t) fc_wanted >= v->nsubs);
	fc_n = (size_t) fc_wanted * 3 / 2 + 1;

	if (v->subs == v->sub10)
	{
		fc_p = (struct subre **) MALLOC(fc_n * sizeof(struct subre *));
		if (fc_p != NULL)
			memcpy(VS(fc_p), VS(v->subs),
				   v->nsubs * sizeof(struct subre *));
	}
	else
		fc_p = (struct subre **) REALLOC(v->subs, fc_n * sizeof(struct subre *));
	if (fc_p == NULL)
	{
		ERR(REG_ESPACE);
		return;
	}
	v->subs = fc_p;
	for (fc_p = &v->subs[v->nsubs]; v->nsubs < fc_n; fc_p++, v->nsubs++)
		*fc_p = NULL;
	assert(v->nsubs == fc_n);
	assert((size_t) fc_wanted < v->nsubs);
}

/*
 * freev - 释放变量结构的子结构（如有必要）
 *
 * 可选择性地设置错误编号，并始终返回错误代码
 * （如果有的话），以使错误处理代码更简洁。
 */
static int freev(struct vars *v,
	  int fc_err)
{
	if (v->re != NULL)
		rfree(v->re);
	if (v->subs != v->sub10)
		FREE(v->subs);
	if (v->nfa != NULL)
		freenfa(v->nfa);
	if (v->tree != NULL)
		freesubre(v, v->tree);
	if (v->treechain != NULL)
		cleanst(v);
	if (v->cv != NULL)
		freecvec(v->cv);
	if (v->cv2 != NULL)
		freecvec(v->cv2);
	if (v->lacons != NULL)
		freelacons(v->lacons, v->nlacons);
	ERR(fc_err);					/* 如果err==0则不做任何操作 */

	return v->err;
}

/*
 * makesearch - 将NFA转化为搜索NFA（隐式添加.*?）
 * NFA必须已经被优化过。
 */
static void makesearch(struct vars *v,
		   struct nfa *fc_nfa)
{
	struct arc *fc_a;
	struct arc *fc_b;
	struct state *fc_pre = fc_nfa->pre;
	struct state *fc_s;
	struct state *fc_s2;
	struct state *fc_slist;

	/* 如果锚定，则不需要循环 */
	for (fc_a = fc_pre->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		assert(fc_a->type == PLAIN);
		if (fc_a->co != fc_nfa->bos[0] && fc_a->co != fc_nfa->bos[1])
			break;
	}
	if (fc_a != NULL)
	{
		/* 在前面添加隐式.* */
		rainbow(fc_nfa, v->cm, PLAIN, COLORLESS, fc_pre, fc_pre);

		/* 还要加^*和\A* -- 虽然并不总是必要，但无害 */
		newarc(fc_nfa, PLAIN, fc_nfa->bos[0], fc_pre, fc_pre);
		newarc(fc_nfa, PLAIN, fc_nfa->bos[1], fc_pre, fc_pre);

		/*
		 * 如果模式之前是MATCHALL，现在最大匹配长度为无限。
		 */
		if (fc_nfa->flags & MATCHALL)
			fc_nfa->maxmatchall = DUPINF;
	}

	/*
	 * 这里是微妙的部分。因为许多RE没有回顾约束，通常知道你何时处于pre状态并不能告诉你很多；下一个状态才是信息丰富的。但是其中一些可能有其他的入弧，即有可能实际取得进展然后再返回其中之一。我们必须对这样的情况进行去优化，将每个这样的状态拆分为进展状态和不进展状态。
	 */

	/* 首先，制作一个从pre和其他地方可达状态的列表 */
	fc_slist = NULL;
	for (fc_a = fc_pre->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		fc_s = fc_a->to;
		for (fc_b = fc_s->ins; fc_b != NULL; fc_b = fc_b->inchain)
		{
			if (fc_b->from != fc_pre)
				break;
		}

		/*
		 * 我们希望通过有非NULL tmp字段来标记状态已经在列表中，但我们不能仅仅将旧的slist值存储在tmp中，因为这对第一个这样的状态不起作用。相反，第一个列表条目在tmp中获取自己的地址。
		 */
		if (fc_b != NULL && fc_s->tmp == NULL)
		{
			fc_s->tmp = (fc_slist != NULL) ? fc_slist : fc_s;
			fc_slist = fc_s;
		}
	}

	/* 进行拆分 */
	for (fc_s = fc_slist; fc_s != NULL; fc_s = fc_s2)
	{
		fc_s2 = newstate(fc_nfa);
		NOERR();
		copyouts(fc_nfa, fc_s, fc_s2);
		NOERR();
		for (fc_a = fc_s->ins; fc_a != NULL; fc_a = fc_b)
		{
			fc_b = fc_a->inchain;
			if (fc_a->from != fc_pre)
			{
				cparc(fc_nfa, fc_a, fc_a->from, fc_s2);
				freearc(fc_nfa, fc_a);
			}
		}
		fc_s2 = (fc_s->tmp != fc_s) ? fc_s->tmp : NULL;
		fc_s->tmp = NULL;			/* 在此时清理 */
	}
}

/*
 * parse - 解析一个RE
 *
 * 这实际上只是顶层，解析一堆通过'|'连接的分支。如果有多个，它们在树中作为'|'子RE的子项出现。
 */
static struct subre * parse(struct vars *v,
	  int fc_stopper,				/* EOS或')' */
	  int fc_type,					/* LACON（前查找子RE）或PLAIN */
	  struct state *fc_init,		/* 初始状态 */
	  struct state *fc_final)		/* 最终状态 */
{
	struct subre *fc_branches;		/* 顶层 */
	struct subre *fc_lastbranch;	/* 最新分支 */

	assert(fc_stopper == ')' || fc_stopper == EOS);

	fc_branches = subre(v, '|', LONGER, fc_init, fc_final);
	NOERRN();
	fc_lastbranch = NULL;
	do
	{							/* a branch */
		struct subre *fc_branch;
		struct state *fc_left;		/* 分支的支架 */
		struct state *fc_right;

		fc_left = newstate(v->nfa);
		fc_right = newstate(v->nfa);
		NOERRN();
		EMPTYARC(fc_init, fc_left);
		EMPTYARC(fc_right, fc_final);
		NOERRN();
		fc_branch = parsebranch(v, fc_stopper, fc_type, fc_left, fc_right, 0);
		NOERRN();
		if (fc_lastbranch)
			fc_lastbranch->sibling = fc_branch;
		else
			fc_branches->child = fc_branch;
		fc_branches->flags |= UP(fc_branches->flags | fc_branch->flags);
		fc_lastbranch = fc_branch;
	} while (EAT('|'));
	assert(SEE(fc_stopper) || SEE(EOS));

	if (!SEE(fc_stopper))
	{
		assert(fc_stopper == ')' && SEE(EOS));
		ERR(REG_EPAREN);
	}

	/* 优化简单情况 */
	if (fc_lastbranch == fc_branches->child)
	{							/* 只有一个分支 */
		assert(fc_lastbranch->sibling == NULL);
		freesrnode(v, fc_branches);
		fc_branches = fc_lastbranch;
	}
	else if (!MESSY(fc_branches->flags))
	{							/* 没有有趣的内部结构 */
		freesubreandsiblings(v, fc_branches->child);
		fc_branches->child = NULL;
		fc_branches->op = '=';
	}

	return fc_branches;
}

/*
 * parsebranch - 解析一个RE的分支
 *
 * 这主要管理连接，与parseqatom()密切合作。连接的事物尽可能地捆绑在一起，仅在由于子结构的需要时引入单独的'.'节点。
 */
static struct subre * parsebranch(struct vars *v,
			int fc_stopper,		/* EOS或')' */
			int fc_type,			/* LACON（前查找子RE）或PLAIN */
			struct state *fc_left, /* 左侧状态 */
			struct state *fc_right,	/* 右侧状态 */
			int fc_partial)		/*这只是一个分支的部分吗？*/
{
	struct state *fc_lp;			/* 当前构造的左端 */
	int			fc_seencontent;	/* 这个分支中还有其他内容吗？ */
	struct subre *fc_t;

	fc_lp = fc_left;
	fc_seencontent = 0;
	fc_t = subre(v, '=', 0, fc_left, fc_right);	/* 操作符 '=' 是暂定的 */
	NOERRN();
	while (!SEE('|') && !SEE(fc_stopper) && !SEE(EOS))
	{
		if (fc_seencontent)
		{						/* 隐式连接操作符 */
			fc_lp = newstate(v->nfa);
			NOERRN();
			moveins(v->nfa, fc_right, fc_lp);
		}
		fc_seencontent = 1;

		/* 注意，parseqatom()中的递归可能会吞掉分支的剩余部分 */
		fc_t = parseqatom(v, fc_stopper, fc_type, fc_lp, fc_right, fc_t);
		NOERRN();
	}

	if (!fc_seencontent)
	{							/* 空分支 */
		if (!fc_partial)
			NOTE(REG_UUNSPEC);
		assert(fc_lp == fc_left);
		EMPTYARC(fc_left, fc_right);
	}

	return fc_t;
}

/*
 * parseqatom - 解析一个量化原子或正则表达式的约束
 *
 * 靠近末尾的记账工作与parsebranch()密切合作；
 * 特别是，它包含一个可能涉及解析分支剩余部分的递归,
 * 使得此函数的名称有点不准确。
 *
 * 通常，返回值只是“顶层”，但在某些情况下，我们
 * 已经解析了分支的其余部分，可能认为“顶层”是多余的并
 * 释放它，返回某个子级子表达式。
 */
static struct subre * parseqatom(struct vars *v,
		   int fc_stopper,			/* EOS或')' */
		   int fc_type,			/* LACON（前查找子RE）或PLAIN */
		   struct state *fc_lp,	/* 挂载的左状态 */
		   struct state *fc_rp,	/* 挂载的右状态 */
		   struct subre *fc_top)	/* 子树顶端 */
{
	struct state *fc_s;			/* 新状态的临时变量 */
	struct state *fc_s2;

#define  ARCV(t, val)	 newarc(v->nfa, t, val, fc_lp, fc_rp)
	int			fc_m,
				fc_n;
	struct subre *fc_atom;			/* 原子的子树 */
	struct subre *fc_t;
	int			fc_cap;			/* 捕获括号？ */
	int			fc_latype;			/* 向前看约束类型 */
	int			fc_subno;			/* 捕获括号或回溯编号 */
	int			fc_atomtype;
	int			fc_qprefer;		/* 量词短/长偏好 */
	int			fc_f;
	struct subre **fc_atomp;		/* 原子指针的位置 */

	/* 初始记账工作 */
	fc_atom = NULL;
	assert(fc_lp->nouts == 0);		/* 必须字符串新的代码 */
	assert(fc_rp->nins == 0);		/* 介于 lp 和 rp 之间 */
	fc_subno = 0;					/* 只是为了让 lint 安静 */

	/* 一个原子或约束... */
	fc_atomtype = v->nexttype;
	switch (fc_atomtype)
	{
			/* 首先，约束，最后返回 */
		case '^':
			ARCV('^', 1);
			if (v->cflags & REG_NLANCH)
				ARCV(BEHIND, v->nlcolor);
			NEXT();
			return fc_top;
			break;
		case '$':
			ARCV('$', 1);
			if (v->cflags & REG_NLANCH)
				ARCV(AHEAD, v->nlcolor);
			NEXT();
			return fc_top;
			break;
		case SBEGIN:
			ARCV('^', 1);		/* BOL */
			ARCV('^', 0);		/* or BOS */
			NEXT();
			return fc_top;
			break;
		case SEND:
			ARCV('$', 1);		/* EOL */
			ARCV('$', 0);		/* or EOS */
			NEXT();
			return fc_top;
			break;
		case '<':
			wordchrs(v);
			fc_s = newstate(v->nfa);
			NOERRN();
			nonword(v, BEHIND, fc_lp, fc_s);
			word(v, AHEAD, fc_s, fc_rp);
			NEXT();
			return fc_top;
			break;
		case '>':
			wordchrs(v);
			fc_s = newstate(v->nfa);
			NOERRN();
			word(v, BEHIND, fc_lp, fc_s);
			nonword(v, AHEAD, fc_s, fc_rp);
			NEXT();
			return fc_top;
			break;
		case WBDRY:
			wordchrs(v);
			fc_s = newstate(v->nfa);
			NOERRN();
			nonword(v, BEHIND, fc_lp, fc_s);
			word(v, AHEAD, fc_s, fc_rp);
			fc_s = newstate(v->nfa);
			NOERRN();
			word(v, BEHIND, fc_lp, fc_s);
			nonword(v, AHEAD, fc_s, fc_rp);
			NEXT();
			return fc_top;
			break;
		case NWBDRY:
			wordchrs(v);
			fc_s = newstate(v->nfa);
			NOERRN();
			word(v, BEHIND, fc_lp, fc_s);
			word(v, AHEAD, fc_s, fc_rp);
			fc_s = newstate(v->nfa);
			NOERRN();
			nonword(v, BEHIND, fc_lp, fc_s);
			nonword(v, AHEAD, fc_s, fc_rp);
			NEXT();
			return fc_top;
			break;
		case LACON:				/* 向前看约束 */
			fc_latype = v->nextvalue;
			NEXT();
			fc_s = newstate(v->nfa);
			fc_s2 = newstate(v->nfa);
			NOERRN();
			fc_t = parse(v, ')', LACON, fc_s, fc_s2);
			freesubre(v, fc_t);	/* 内部结构无关紧要 */
			NOERRN();
			assert(SEE(')'));
			NEXT();
			processlacon(v, fc_s, fc_s2, fc_latype, fc_lp, fc_rp);
			return fc_top;
			break;
			/* 然后是错误，以便把它们清除 */
		case '*':
		case '+':
		case '?':
		case '{':
			ERR(REG_BADRPT);
			return fc_top;
			break;
		default:
			ERR(REG_ASSERT);
			return fc_top;
			break;
			/* 然后是普通字符，以及在这个主题上的小变体 */
		case ')':				/* 不平衡的括号 */
			if ((v->cflags & REG_ADVANCED) != REG_EXTENDED)
			{
				ERR(REG_EPAREN);
				return fc_top;
			}
			/* 由于规格错误在 ERE 中合法 */
			NOTE(REG_UPBOTCH);
			/* 落入 PLAIN 样式的 case */
			/* FALLTHROUGH */
		case PLAIN:
			onechr(v, v->nextvalue, fc_lp, fc_rp);
			okcolors(v->nfa, v->cm);
			NOERRN();
			NEXT();
			break;
		case '[':
			if (v->nextvalue == 1)
				bracket(v, fc_lp, fc_rp);
			else
				cbracket(v, fc_lp, fc_rp);
			assert(SEE(']') || ISERR());
			NEXT();
			break;
		case CCLASSS:
			charclass(v, (enum char_classes) v->nextvalue, fc_lp, fc_rp);
			okcolors(v->nfa, v->cm);
			NEXT();
			break;
		case CCLASSC:
			charclasscomplement(v, (enum char_classes) v->nextvalue, fc_lp, fc_rp);
			/* charclasscomplement() 在内部完成了 okcolors() */
			NEXT();
			break;
		case '.':
			rainbow(v->nfa, v->cm, PLAIN,
					(v->cflags & REG_NLSTOP) ? v->nlcolor : COLORLESS,
					fc_lp, fc_rp);
			NEXT();
			break;
			/* 最终是难看的东西 */
		case '(':				/* 值标志为捕获或非捕获 */
			fc_cap = (fc_type == LACON) ? 0 : v->nextvalue;
			if (fc_cap)
			{
				v->nsubexp++;
				fc_subno = v->nsubexp;
				if ((size_t) fc_subno >= v->nsubs)
					moresubs(v, fc_subno);
			}
			else
				fc_atomtype = PLAIN;	/* 一些不是 '(' 的东西 */
			NEXT();

			/*
			 * 制作单独的端点状态，以使此子 NFA 与周围的内容保持区分
			 * 我们必须确保在为 backref 复制子 NFA 时，获取正确的
			 * 状态/弧形，而没有其他状态。特别是，让 backref
			 * 从 lp 复制子 NFA 到 rp 是非常错误的，
			 * 因为我们可能会在下面的原子周围添加量词结构。
			 * （也许我们可以跳过非捕获性括号的额外状态，但这似乎不值得。）
			 */
			fc_s = newstate(v->nfa);
			fc_s2 = newstate(v->nfa);
			NOERRN();
			/* 我们可能不需要这些弧形，但现在保持连接 */
			EMPTYARC(fc_lp, fc_s);
			EMPTYARC(fc_s2, fc_rp);
			NOERRN();
			fc_atom = parse(v, ')', fc_type, fc_s, fc_s2);
			assert(SEE(')') || ISERR());
			NEXT();
			NOERRN();
			if (fc_cap)
			{
				if (fc_atom->capno == 0)
				{
					/* 正常情况：只需将原子标记为捕获 */
					fc_atom->flags |= CAP;
					fc_atom->capno = fc_subno;
				}
				else
				{
					/* 生成无操作包装节点以处理 "((x))" */
					fc_t = subre(v, '(', fc_atom->flags | CAP, fc_s, fc_s2);
					NOERRN();
					fc_t->capno = fc_subno;
					fc_t->child = fc_atom;
					fc_atom = fc_t;
				}
				assert(v->subs[fc_subno] == NULL);
				v->subs[fc_subno] = fc_atom;
			}
			/* 推迟其他所有内容，以待可能出现的 {0} */
			break;
		case BACKREF:			/* 来自黑色沼泽的特性 */
			INSIST(fc_type != LACON, REG_ESUBREG);
			fc_subno = v->nextvalue;
			assert(fc_subno > 0);
			INSIST(fc_subno < v->nsubs, REG_ESUBREG);
			NOERRN();
			INSIST(v->subs[fc_subno] != NULL, REG_ESUBREG);
			NOERRN();
			fc_atom = subre(v, 'b', BACKR, fc_lp, fc_rp);
			NOERRN();
			fc_atom->backno = fc_subno;
			v->subs[fc_subno]->flags |= BRUSE;
			EMPTYARC(fc_lp, fc_rp);	/* 暂时，因此有一些东西 */
			NEXT();
			break;
	}

	/* ...和一个原子可能会被量词跟随 */
	switch (v->nexttype)
	{
		case '*':
			fc_m = 0;
			fc_n = DUPINF;
			fc_qprefer = (v->nextvalue) ? LONGER : SHORTER;
			NEXT();
			break;
		case '+':
			fc_m = 1;
			fc_n = DUPINF;
			fc_qprefer = (v->nextvalue) ? LONGER : SHORTER;
			NEXT();
			break;
		case '?':
			fc_m = 0;
			fc_n = 1;
			fc_qprefer = (v->nextvalue) ? LONGER : SHORTER;
			NEXT();
			break;
		case '{':
			NEXT();
			fc_m = scannum(v);
			if (EAT(','))
			{
				if (SEE(DIGIT))
					fc_n = scannum(v);
				else
					fc_n = DUPINF;
				if (fc_m > fc_n)
				{
					ERR(REG_BADBR);
					return fc_top;
				}
				/* {m,n} 优先，尽管它是 {m,m} */
				fc_qprefer = (v->nextvalue) ? LONGER : SHORTER;
			}
			else
			{
				fc_n = fc_m;
				/* {m} 传递操作数的优先级 */
				fc_qprefer = 0;
			}
			if (!SEE('}'))
			{					/* 也捕捉错误 */
				ERR(REG_BADBR);
				return fc_top;
			}
			NEXT();
			break;
		default:				/* 没有量词 */
			fc_m = fc_n = 1;
			fc_qprefer = 0;
			break;
	}

	/* 令人烦恼的特殊情况：{0} 或 {0,0} 取消一切 */
	if (fc_m == 0 && fc_n == 0)
	{
		/*
		 * 如果我们在原子内有捕获子表达式，我们不想
		 * 销毁它们，因为合法（如果无用）在后面反向引用它们。
		 * 因此，只需将原子与 lp/rp 解除链接，然后忽略它。
		 */
		if (fc_atom != NULL && (fc_atom->flags & CAP))
		{
			delsub(v->nfa, fc_lp, fc_atom->begin);
			delsub(v->nfa, fc_atom->end, fc_rp);
		}
		else
		{
			/* 否则，我们可以清理我们创建的任何 subre 基础设施 */
			if (fc_atom != NULL)
				freesubre(v, fc_atom);
			delsub(v->nfa, fc_lp, fc_rp);
		}
		EMPTYARC(fc_lp, fc_rp);
		return fc_top;
	}

	/* 如果不是麻烦的情况，避免难点 */
	assert(!MESSY(fc_top->flags));
	fc_f = fc_top->flags | fc_qprefer | ((fc_atom != NULL) ? fc_atom->flags : 0);
	if (fc_atomtype != '(' && fc_atomtype != BACKREF && !MESSY(UP(fc_f)))
	{
		if (!(fc_m == 1 && fc_n == 1))
			repeat(v, fc_lp, fc_rp, fc_m, fc_n);
		if (fc_atom != NULL)
			freesubre(v, fc_atom);
		fc_top->flags = fc_f;
		return fc_top;
	}

	/*
	 * 难点：一些麻烦的事情
	 *
	 * 也就是说，捕获括号、反向引用、短/长冲突，或者一个
	 * 包含其中一个的子结构的原子。
	 */

	/* 现在我们需要一个 subre 来处理内容，即使它们很无聊 */
	if (fc_atom == NULL)
	{
		fc_atom = subre(v, '=', 0, fc_lp, fc_rp);
		NOERRN();
	}

	/*
	 * 在接下来的内容中，我们需要原子有自己的起始/结束状态
	 * 与 lp/rp 不同，以便我们可以在其周围包裹迭代结构。
	 * 上面的括号原子情况已经生成了适当的状态
	 * （而且我们不想修改捕获的 subre，因为它已经记录在 v->subs[] 中）。
	 * 否则，我们需要更多的状态。
	 */
	if (fc_atom->begin == fc_lp || fc_atom->end == fc_rp)
	{
		fc_s = newstate(v->nfa);
		fc_s2 = newstate(v->nfa);
		NOERRN();
		moveouts(v->nfa, fc_lp, fc_s);
		moveins(v->nfa, fc_rp, fc_s2);
		fc_atom->begin = fc_s;
		fc_atom->end = fc_s2;
	}
	else
	{
		/* 原子可以，但我们必须暂时将其从 lp/rp 断开 */
		/* （这将移除我们上面制作的 EMPTY 弧形） */
		delsub(v->nfa, fc_lp, fc_atom->begin);
		delsub(v->nfa, fc_atom->end, fc_rp);
	}

	/*----------
	 * 准备一个通用状态骨架。
	 *
	 * 在没有反向引用的情况下，我们想要这个：
	 *
	 * [lp] ---> [s] ---prefix---> ---atom---> ---rest---> [rp]
	 *
	 * 其中 prefix 是原子的一些重复，而 "rest" 是分支的其余部分。
	 * 在一般情况下，我们需要：
	 *
	 * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
	 *
	 * 其中迭代器包裹在原子周围。
	 *
	 * 我们在这里为两种情况创建 s 状态；如果需要，在下方创建 s2
	 *----------
	 */
	fc_s = newstate(v->nfa);		/* 设置起始状态 */
	NOERRN();
	EMPTYARC(fc_lp, fc_s);
	NOERRN();

	/* 将剩余的 subRE 拆分为 x{...} 和后面的内容 */
	fc_t = subre(v, '.', COMBINE(fc_qprefer, fc_atom->flags), fc_lp, fc_rp);
	NOERRN();
	fc_t->child = fc_atom;
	fc_atomp = &fc_t->child;

	/*
	 * 在这里我们应该递归填充 t->child->sibling ... 但我们必须
	 * 将其推迟到最后。一个原因是 t->child 可能在下面被替换，
	 * 我们不想担心它的兄弟链接。
	 */

	/*
	 * 将顶部节点转换为前缀（top->child，覆盖我们之前解析的内容）和剩余部分（t）的串联。注意，前缀可能为空，这种情况下这个串联节点是多余的。为了保持简单，我们现在以一般的方式操作，并去掉下面不必要的子节点。
	 */
	assert(fc_top->op == '=' && fc_top->child == NULL);
	fc_top->child = subre(v, '=', fc_top->flags, fc_top->begin, fc_lp);
	NOERRN();
	fc_top->op = '.';
	fc_top->child->sibling = fc_t;
	/* top->flags 将在稍后更新 */

	/* 如果是反向引用，现在是复制子NFA的时机 */
	if (fc_atomtype == BACKREF)
	{
		assert(fc_atom->begin->nouts == 1);	/* 只是 EMPTY */
		delsub(v->nfa, fc_atom->begin, fc_atom->end);
		assert(v->subs[fc_subno] != NULL);

		/*
		 * 这就是递归推迟的原因：它必须等到骨架填充完成，因为它可能会遇到想要复制已填充骨架的反向引用。
		 */
		dupnfa(v->nfa, v->subs[fc_subno]->begin, v->subs[fc_subno]->end,
			   fc_atom->begin, fc_atom->end);
		NOERRN();

		/* 反向引用节点的 NFA 不应该强制任何约束 */
		removeconstraints(v->nfa, fc_atom->begin, fc_atom->end);
		NOERRN();
	}

	/*
	 * 现在是量词时间。如果原子只是一个反向引用，我们将让它在内部处理量词。
	 */
	if (fc_atomtype == BACKREF)
	{
		/* 特殊情况：反向引用具有内部量词 */
		EMPTYARC(fc_s, fc_atom->begin);	/* 空前缀 */
		/* 只是将一切都放入原子中 */
		repeat(v, fc_atom->begin, fc_atom->end, fc_m, fc_n);
		fc_atom->min = (short) fc_m;
		fc_atom->max = (short) fc_n;
		fc_atom->flags |= COMBINE(fc_qprefer, fc_atom->flags);
		/* 剩余分支可以从 atom->end 开始串联 */
		fc_s2 = fc_atom->end;
	}
	else if (fc_m == 1 && fc_n == 1 &&
			 (fc_qprefer == 0 ||
			  (fc_atom->flags & (LONGER | SHORTER | MIXED)) == 0 ||
			  fc_qprefer == (fc_atom->flags & (LONGER | SHORTER | MIXED))))
	{
		/* 无/无效量词：完成 */
		EMPTYARC(fc_s, fc_atom->begin);	/* 空前缀 */
		/* 剩余分支可以从 atom->end 开始串联 */
		fc_s2 = fc_atom->end;
	}
	else if (!(fc_atom->flags & (CAP | BACKR)))
	{
		/*
		 * 如果在被重复的原子中没有捕获或反向引用，我们实际上并不关心迭代的子匹配在哪里，因此我们不需要一个迭代节点。可以改为创建一个普通的 DFA 节点。
		 */
		EMPTYARC(fc_s, fc_atom->begin);	/* 空前缀 */
		repeat(v, fc_atom->begin, fc_atom->end, fc_m, fc_n);
		fc_f = COMBINE(fc_qprefer, fc_atom->flags);
		fc_t = subre(v, '=', fc_f, fc_atom->begin, fc_atom->end);
		NOERRN();
		freesubre(v, fc_atom);
		*fc_atomp = fc_t;
		/* 剩余分支可以从 t->end 开始串联 */
		fc_s2 = fc_t->end;
	}
	else if (fc_m > 0 && !(fc_atom->flags & BACKR))
	{
		/*
		 * 如果没有反向引用，我们可以将 x{m,n} 转换为 x{m-1,n-1}x，且捕获括号仅在第二个 x 中。这是有效的，因为我们只关心量词的最终迭代捕获的匹配。这是一个优势，因为我们可以将无反向引用的左侧实现为普通的 DFA 节点，因为我们实际上并不关心其子匹配在哪里。
		 */
		dupnfa(v->nfa, fc_atom->begin, fc_atom->end, fc_s, fc_atom->begin);
		assert(fc_m >= 1 && fc_m != DUPINF && fc_n >= 1);
		repeat(v, fc_s, fc_atom->begin, fc_m - 1, (fc_n == DUPINF) ? fc_n : fc_n - 1);
		fc_f = COMBINE(fc_qprefer, fc_atom->flags);
		fc_t = subre(v, '.', fc_f, fc_s, fc_atom->end); /* 前缀和原子 */
		NOERRN();
		fc_t->child = subre(v, '=', PREF(fc_f), fc_s, fc_atom->begin);
		NOERRN();
		fc_t->child->sibling = fc_atom;
		*fc_atomp = fc_t;
		/* 剩余分支可以从 atom->end 开始串联 */
		fc_s2 = fc_atom->end;
	}
	else
	{
		/* 一般情况：需要一个迭代节点 */
		fc_s2 = newstate(v->nfa);
		NOERRN();
		moveouts(v->nfa, fc_atom->end, fc_s2);
		NOERRN();
		dupnfa(v->nfa, fc_atom->begin, fc_atom->end, fc_s, fc_s2);
		repeat(v, fc_s, fc_s2, fc_m, fc_n);
		fc_f = COMBINE(fc_qprefer, fc_atom->flags);
		fc_t = subre(v, '*', fc_f, fc_s, fc_s2);
		NOERRN();
		fc_t->min = (short) fc_m;
		fc_t->max = (short) fc_n;
		fc_t->child = fc_atom;
		*fc_atomp = fc_t;
		/* 剩余分支将从迭代的结束状态进行串联 */
	}

	/* 最后，处理那被推迟的递归 */
	fc_t = fc_top->child->sibling;
	if (!(SEE('|') || SEE(fc_stopper) || SEE(EOS)))
	{
		/* 解析分支的其余部分，并插入到 t->child->sibling 中 */
		fc_t->child->sibling = parsebranch(v, fc_stopper, fc_type, fc_s2, fc_rp, 1);
		NOERRN();
		assert(SEE('|') || SEE(fc_stopper) || SEE(EOS));

		/* 这是承诺的 flags 更新 */
		fc_t->flags |= COMBINE(fc_t->flags, fc_t->child->sibling->flags);
		fc_top->flags |= COMBINE(fc_top->flags, fc_t->flags);

		/* 现在 t 和 top 都尚未被直接标记为捕获 */
		assert(fc_t->capno == 0);
		assert(fc_top->capno == 0);

		/*
		 * 此时，top 和 t 都是串联（op == '.'）子节点，我们有 top->child = 分支的前缀，top->child->sibling = t，t->child = 稍显复杂的原子（如有需要则含量词超结构），t->child->sibling = 分支的剩余部分。
		 *
		 * 如果稍显复杂的原子是分支中的第一个东西，那么 top->child 是无效的，我们可以去掉一层串联。
		 */
		assert(fc_top->child->op == '=');
		if (fc_top->child->begin == fc_top->child->end)
		{
			assert(!MESSY(fc_top->child->flags));
			freesubre(v, fc_top->child);
			fc_top->child = fc_t->child;
			freesrnode(v, fc_t);
		}

		/*
		 * 否则，t->child 有可能本身并不复杂，但由于其贪婪性与之前的内容相冲突，我们认为它复杂。然后 t->child 和剩余分支的组合可能也不复杂，在这种情况下，我们可以通过将 t->child 和剩余分支合并为一个普通的 DFA 节点来去掉子串联。
		 */
		else if (fc_t->child->op == '=' &&
				 fc_t->child->sibling->op == '=' &&
				 !MESSY(UP(fc_t->child->flags | fc_t->child->sibling->flags)))
		{
			fc_t->op = '=';
			fc_t->flags = COMBINE(fc_t->child->flags, fc_t->child->sibling->flags);
			freesubreandsiblings(v, fc_t->child);
			fc_t->child = NULL;
		}
	}
	else
	{
		/*
		 * 分支中没有其他内容，因此我们不需要第二个串联节点 't'。只需将 s2 直接链接到 rp。
		 */
		EMPTYARC(fc_s2, fc_rp);
		fc_top->child->sibling = fc_t->child;
		fc_top->flags |= COMBINE(fc_top->flags, fc_top->child->sibling->flags);
		freesrnode(v, fc_t);

		/*
		 * 再次强调，top->child 可能是无效的（如果稍显复杂的原子实际上是分支中唯一的东西）。在这种情况下，我们根本不需要串联; 只需用 top->child->sibling 替换 top。
		 */
		assert(fc_top->child->op == '=');
		if (fc_top->child->begin == fc_top->child->end)
		{
			assert(!MESSY(fc_top->child->flags));
			fc_t = fc_top->child->sibling;
			fc_top->child->sibling = NULL;
			freesubre(v, fc_top);
			fc_top = fc_t;
		}
	}

	return fc_top;
}

/*
 * 非字 - 为非单词字符前后的弧生成
 */
static void nonword(struct vars *v,
		int fc_dir,				/* 前面或后面 */
		struct state *fc_lp,
		struct state *fc_rp)
{
	int			fc_anchor = (fc_dir == AHEAD) ? '$' : '^';

	assert(fc_dir == AHEAD || fc_dir == BEHIND);
	newarc(v->nfa, fc_anchor, 1, fc_lp, fc_rp);
	newarc(v->nfa, fc_anchor, 0, fc_lp, fc_rp);
	colorcomplement(v->nfa, v->cm, fc_dir, v->wordchrs, fc_lp, fc_rp);
	/* （无需特别关注 \n） */
}

/*
 * word - 为前后字符生成弧
 */
static void word(struct vars *v,
	 int fc_dir,					/* 前面或后面 */
	 struct state *fc_lp,
	 struct state *fc_rp)
{
	assert(fc_dir == AHEAD || fc_dir == BEHIND);
	cloneouts(v->nfa, v->wordchrs, fc_lp, fc_rp, fc_dir);
	/* （无需特别关注 \n） */
}

/*
 * charclass - 为字符类生成弧
 *
 * 这用于原子（\w 和兄弟转义）以及括号表达式的元素。调用者负责在处理原子或括号结束时调用 okcolors()。
 */
static void charclass(struct vars *v,
		  enum char_classes fc_cls,
		  struct state *fc_lp,
		  struct state *fc_rp)
{
	struct cvec *fc_cv;

	/* 获取可能已缓存的 cvec 用于字符类 */
	NOTE(REG_ULOCALE);
	fc_cv = cclasscvec(v, fc_cls, (v->cflags & REG_ICASE));
	NOERR();

	/* 构建弧；这可能导致颜色分裂 */
	subcolorcvec(v, fc_cv, fc_lp, fc_rp);
}

/*
 * charclasscomplement - 为补充的字符类生成弧
 *
 * 这用于原子（\W 和兄弟转义）以及括号表达式的元素。在括号表达式中，调用者负责确保在调用时没有开放的子颜色。
 */
static void charclasscomplement(struct vars *v,
					enum char_classes fc_cls,
					struct state *fc_lp,
					struct state *fc_rp)
{
	struct state *fc_cstate;
	struct cvec *fc_cv;

	/* 创建虚拟状态以挂载临时弧 */
	fc_cstate = newstate(v->nfa);
	NOERR();

	/* 获取可能已缓存的 cvec 用于字符类 */
	NOTE(REG_ULOCALE);
	fc_cv = cclasscvec(v, fc_cls, (v->cflags & REG_ICASE));
	NOERR();

	/* 为字符类构建弧；这可能导致颜色分裂 */
	subcolorcvec(v, fc_cv, fc_cstate, fc_cstate);
	NOERR();

	/* 清理弧集中任何子颜色 */
	okcolors(v->nfa, v->cm);
	NOERR();

	/* 现在为字符类的补集构建输出弧 */
	colorcomplement(v->nfa, v->cm, PLAIN, fc_cstate, fc_lp, fc_rp);
	NOERR();

	/* 清理虚拟状态 */
	dropstate(v->nfa, fc_cstate);
}

/*
 * scannum - 扫描一个数字
 */
static int						/* 值，<= DUPMAX */
scannum(struct vars *v)
{
	int			fc_n = 0;

	while (SEE(DIGIT) && fc_n < DUPMAX)
	{
		fc_n = fc_n * 10 + v->nextvalue;
		NEXT();
	}
	if (SEE(DIGIT) || fc_n > DUPMAX)
	{
		ERR(REG_BADBR);
		return 0;
	}
	return fc_n;
}

/*
 * repeat - 为量词复制子NFA
 *
 * 从 lp 到 rp 的子-NFA 被修改以表示其初始内容的 m 到 n 次重复。
 *
 * 这里使用的重复序列经过精心选择，以便任何开始指向子表达式的指针最终指向最后一个出现。（请注意，它可能并不串联在相同的左右端状态之间！）这对 subRE 树曾经很重要，尽管重要部分现在由 parse() 中的内联代码处理，调用时就不再重要了。
 */
static void repeat(struct vars *v,
	   struct state *fc_lp,
	   struct state *fc_rp,
	   int fc_m,
	   int fc_n)
{
#define  SOME	 2
#define  INF	 3
#define  PAIR(x, y)  ((x)*4 + (y))
#define  REDUCE(x)	 ( ((x) == DUPINF) ? INF : (((x) > 1) ? SOME : (x)) )
	const int	fc_rm = REDUCE(fc_m);
	const int	fc_rn = REDUCE(fc_n);
	struct state *fc_s;
	struct state *fc_s2;

	switch (PAIR(fc_rm, fc_rn))
	{
		case PAIR(0, 0):		/* 空字符串 */
			delsub(v->nfa, fc_lp, fc_rp);
			EMPTYARC(fc_lp, fc_rp);
			break;
		case PAIR(0, 1):		/* do as x| */
			EMPTYARC(fc_lp, fc_rp);
			break;
		case PAIR(0, SOME):		/* 执行 x{1,n}| */
			repeat(v, fc_lp, fc_rp, 1, fc_n);
			NOERR();
			EMPTYARC(fc_lp, fc_rp);
			break;
		case PAIR(0, INF):		/* 使 x 循环 */
			fc_s = newstate(v->nfa);
			NOERR();
			moveouts(v->nfa, fc_lp, fc_s);
			moveins(v->nfa, fc_rp, fc_s);
			EMPTYARC(fc_lp, fc_s);
			EMPTYARC(fc_s, fc_rp);
			break;
		case PAIR(1, 1):		/* 无需采取行动 */
			break;
		case PAIR(1, SOME):		/* 执行 x{0,n-1}x = (x{1,n-1}|)x */
			fc_s = newstate(v->nfa);
			NOERR();
			moveouts(v->nfa, fc_lp, fc_s);
			dupnfa(v->nfa, fc_s, fc_rp, fc_lp, fc_s);
			NOERR();
			repeat(v, fc_lp, fc_s, 1, fc_n - 1);
			NOERR();
			EMPTYARC(fc_lp, fc_s);
			break;
		case PAIR(1, INF):		/* 添加回环弧 */
			fc_s = newstate(v->nfa);
			fc_s2 = newstate(v->nfa);
			NOERR();
			moveouts(v->nfa, fc_lp, fc_s);
			moveins(v->nfa, fc_rp, fc_s2);
			EMPTYARC(fc_lp, fc_s);
			EMPTYARC(fc_s2, fc_rp);
			EMPTYARC(fc_s2, fc_s);
			break;
		case PAIR(SOME, SOME):	/* 执行 x{m-1,n-1}x */
			fc_s = newstate(v->nfa);
			NOERR();
			moveouts(v->nfa, fc_lp, fc_s);
			dupnfa(v->nfa, fc_s, fc_rp, fc_lp, fc_s);
			NOERR();
			repeat(v, fc_lp, fc_s, fc_m - 1, fc_n - 1);
			break;
		case PAIR(SOME, INF):	/* 执行 x{m-1,}x */
			fc_s = newstate(v->nfa);
			NOERR();
			moveouts(v->nfa, fc_lp, fc_s);
			dupnfa(v->nfa, fc_s, fc_rp, fc_lp, fc_s);
			NOERR();
			repeat(v, fc_lp, fc_s, fc_m - 1, fc_n);
			break;
		default:
			ERR(REG_ASSERT);
			break;
	}
}

/*
 * bracket - 处理非补充的括号表达式
 *
 * 也可以从 cbracket 调用以处理补充的括号表达式。
 */
static void bracket(struct vars *v,
		struct state *fc_lp,
		struct state *fc_rp)
{
	/*
	 * 我们不能在扫描括号表达式时立即处理补充字符类（例如 \W），否则颜色记录会混淆。
	 * 相反，记住我们在 have_cclassc[] 中是否见过任何，然后在最后进行处理。
	 */
	bool		fc_have_cclassc[NUM_CCLASSES];
	bool		fc_any_cclassc;
	int			fc_i;

	memset(fc_have_cclassc, false, sizeof(fc_have_cclassc));

	assert(SEE('['));
	NEXT();
	while (!SEE(']') && !SEE(EOS))
		brackpart(v, fc_lp, fc_rp, fc_have_cclassc);
	assert(SEE(']') || ISERR());

	/* 关闭来自正括号元素的开放子颜色 */
	okcolors(v->nfa, v->cm);
	NOERR();

	/* 现在处理任何补充元素 */
	fc_any_cclassc = false;
	for (fc_i = 0; fc_i < NUM_CCLASSES; fc_i++)
	{
		if (fc_have_cclassc[fc_i])
		{
			charclasscomplement(v, (enum char_classes) fc_i, fc_lp, fc_rp);
			NOERR();
			fc_any_cclassc = true;
		}
	}

	/*
	 * 如果我们有任何补充元素，看看我们是否可以将括号优化为彩虹。
	 * 由于补充元素是白色弧进入结果的唯一方法，因此没有必要再进行其他检查。
	 */
	if (fc_any_cclassc)
		optimizebracket(v, fc_lp, fc_rp);
}

/*
 * cbracket - 处理补充的括号表达式
 *
 * 我们通过调用 bracket() 及虚拟端点，然后补充结果来实现。
 * 替代方法是调用 rainbow()，然后在看到 b.e. 时删除弧……但是这会变得很麻烦，并且在 rainbow() 只输出一个 RAINBOW 弧时实际上是相当不可行的。
 */
static void cbracket(struct vars *v,
		 struct state *fc_lp,
		 struct state *fc_rp)
{
	struct state *fc_left = newstate(v->nfa);
	struct state *fc_right = newstate(v->nfa);

	NOERR();
	bracket(v, fc_left, fc_right);

	/* 在 NLSTOP 模式下，确保换行符不属于结果集 */
	if (v->cflags & REG_NLSTOP)
		newarc(v->nfa, PLAIN, v->nlcolor, fc_left, fc_right);
	NOERR();

	assert(fc_lp->nouts == 0);		/* 所有输出弧将是我们的 */

	/*
	 * 补充的简单部分，自从移除了 MCCE 代码之后就没有其他事情要做。
	 * 注意 colorcomplement() 的结果不能是彩虹，因为我们不允许空括号；所以再次调用 optimizebracket() 并没有意义。
	 */
	colorcomplement(v->nfa, v->cm, PLAIN, fc_left, fc_lp, fc_rp);
	NOERR();
	dropstate(v->nfa, fc_left);
	assert(fc_right->nins == 0);
	freestate(v->nfa, fc_right);
}

/*
 * brackpart - 处理括号表达式中的一个项目（或范围）
 */
static void brackpart(struct vars *v,
		  struct state *fc_lp,
		  struct state *fc_rp,
		  bool *fc_have_cclassc)
{
	chr			fc_startc;
	chr			fc_endc;
	struct cvec *fc_cv;
	enum char_classes fc_cls;
	const chr  *fc_startp;
	const chr  *fc_endp;

	/* 解析某些内容，去掉特殊情况，采取捷径 */
	switch (v->nexttype)
	{
		case RANGE:				/* a-b-c 或其他错误情况 */
			ERR(REG_ERANGE);
			return;
			break;
		case PLAIN:
			fc_startc = v->nextvalue;
			NEXT();
			/* 普通字符的捷径（不是范围） */
			if (!SEE(RANGE))
			{
				onechr(v, fc_startc, fc_lp, fc_rp);
				return;
			}
			NOERR();
			break;
		case COLLEL:
			fc_startp = v->now;
			fc_endp = scanplain(v);
			INSIST(fc_startp < fc_endp, REG_ECOLLATE);
			NOERR();
			fc_startc = element(v, fc_startp, fc_endp);
			NOERR();
			break;
		case ECLASS:
			fc_startp = v->now;
			fc_endp = scanplain(v);
			INSIST(fc_startp < fc_endp, REG_ECOLLATE);
			NOERR();
			fc_startc = element(v, fc_startp, fc_endp);
			NOERR();
			fc_cv = eclass(v, fc_startc, (v->cflags & REG_ICASE));
			NOERR();
			subcolorcvec(v, fc_cv, fc_lp, fc_rp);
			return;
			break;
		case CCLASS:
			fc_startp = v->now;
			fc_endp = scanplain(v);
			INSIST(fc_startp < fc_endp, REG_ECTYPE);
			NOERR();
			fc_cls = lookupcclass(v, fc_startp, fc_endp);
			NOERR();
			charclass(v, fc_cls, fc_lp, fc_rp);
			return;
			break;
		case CCLASSS:
			charclass(v, (enum char_classes) v->nextvalue, fc_lp, fc_rp);
			NEXT();
			return;
			break;
		case CCLASSC:
			/* 我们无法立即调用 charclasscomplement() */
			fc_have_cclassc[v->nextvalue] = true;
			NEXT();
			return;
			break;
		default:
			ERR(REG_ASSERT);
			return;
			break;
	}

	if (SEE(RANGE))
	{
		NEXT();
		switch (v->nexttype)
		{
			case PLAIN:
			case RANGE:
				fc_endc = v->nextvalue;
				NEXT();
				NOERR();
				break;
			case COLLEL:
				fc_startp = v->now;
				fc_endp = scanplain(v);
				INSIST(fc_startp < fc_endp, REG_ECOLLATE);
				NOERR();
				fc_endc = element(v, fc_startp, fc_endp);
				NOERR();
				break;
			default:
				ERR(REG_ERANGE);
				return;
				break;
		}
	}
	else
		fc_endc = fc_startc;

	/*
	 * 范围是不便移植的。实际上，标准 C 确保数字是连续的，
	 * 但将其作为例外处理实在是太复杂了。
	 */
	if (fc_startc != fc_endc)
		NOTE(REG_UUNPORT);
	fc_cv = range(v, fc_startc, fc_endc, (v->cflags & REG_ICASE));
	NOERR();
	subcolorcvec(v, fc_cv, fc_lp, fc_rp);
}

/*
 * scanplain - 扫描 [. 等的普通内容
 *
 * regc_lex.c 中某些技巧知道此代码不会尝试超出 [. 等的最后一个括号。
 */
static const chr *				/* 就在序列结束后 */
scanplain(struct vars *v)
{
	const chr  *fc_endp;

	assert(SEE(COLLEL) || SEE(ECLASS) || SEE(CCLASS));
	NEXT();

	fc_endp = v->now;
	while (SEE(PLAIN))
	{
		fc_endp = v->now;
		NEXT();
	}

	assert(SEE(END) || ISERR());
	NEXT();

	return fc_endp;
}

/*
 * onechr - 为一个普通字符填充弧线，以及可能的大小写补充
 * 这主要是为了高效处理常见情况的捷径。
 */
static void onechr(struct vars *v,
	   chr fc_c,
	   struct state *fc_lp,
	   struct state *fc_rp)
{
	if (!(v->cflags & REG_ICASE))
	{
		color		fc_lastsubcolor = COLORLESS;

		subcoloronechr(v, fc_c, fc_lp, fc_rp, &fc_lastsubcolor);
		return;
	}

	/* 糟糕，反正需要一般情况... */
	subcolorcvec(v, allcases(v, fc_c), fc_lp, fc_rp);
}

/*
 * optimizebracket - 查看括号表达式是否可以转换为 RAINBOW
 *
 * 像 "[\s\S]" 这样的情况可以产生所有颜色的弧线集，
 * 我们可以用一个 RAINBOW 弧线替换它以提高效率。（这可能看起来
 * 像是以一种愚蠢的方式写 "."，但在其他一些类型的正则表达式中
 * 这似乎是一个常见的表述，所以费心好好支持它。）
 */
static void optimizebracket(struct vars *v,
				struct state *fc_lp,
				struct state *fc_rp)
{
	struct colordesc *fc_cd;
	struct colordesc *fc_end = CDEND(v->cm);
	struct arc *fc_a;
	bool		fc_israinbow;

	/*
	 * 扫描 lp 的出弧并暂时标记提到的颜色。我们
	 * 预计 lp 的所有出弧都是普通的、非 RAINBOW 的弧线到 rp。
	 * （注意：目前不应该有任何伪颜色，但还是要检查。）
	 */
	for (fc_a = fc_lp->outs; fc_a != NULL; fc_a = fc_a->outchain)
	{
		assert(fc_a->type == PLAIN);
		assert(fc_a->co >= 0);		/* 即不是 RAINBOW */
		assert(fc_a->to == fc_rp);
		fc_cd = &v->cm->cd[fc_a->co];
		assert(!UNUSEDCOLOR(fc_cd) && !(fc_cd->flags & PSEUDO));
		fc_cd->flags |= COLMARK;
	}

	/* 扫描颜色，清除暂时标记，检查未标记的活动颜色 */
	fc_israinbow = true;
	for (fc_cd = v->cm->cd; fc_cd < fc_end; fc_cd++)
	{
		if (fc_cd->flags & COLMARK)
			fc_cd->flags &= ~COLMARK;
		else if (!UNUSEDCOLOR(fc_cd) && !(fc_cd->flags & PSEUDO))
			fc_israinbow = false;
	}

	/* 如果并非所有颜色都有弧线，则无法执行任何操作 */
	if (!fc_israinbow)
		return;

	/* 好吧，丢弃现有弧线并替换为彩虹 */
	while ((fc_a = fc_lp->outs) != NULL)
		freearc(v->nfa, fc_a);
	newarc(v->nfa, PLAIN, RAINBOW, fc_lp, fc_rp);
}

/*
 * wordchrs - 为单词边界相关内容设置 word-chr 列表（如需要）
 *
 * 该列表保持为一组循环弧线，附加在一个未使用的状态上。
 *
 * 请注意，这个函数在我们有任何开放的子颜色时不能被调用，
 * 否则列表的构建会混淆颜色记账。
 * 因此，我们目前无法在 charclass[complement]() 中应用类似的优化，
 * 因为这些需要可用于括号表达式内。
 */
static void wordchrs(struct vars *v)
{
	struct state *fc_cstate;
	struct cvec *fc_cv;

	if (v->wordchrs != NULL)
		return;					/* 已经完成 */

	/* 制作虚拟状态以挂载缓存弧线 */
	fc_cstate = newstate(v->nfa);
	NOERR();

	/* 获取可能缓存的 \w 字符的 cvec */
	NOTE(REG_ULOCALE);
	fc_cv = cclasscvec(v, CC_WORD, (v->cflags & REG_ICASE));
	NOERR();

	/* 构建弧；这可能导致颜色分裂 */
	subcolorcvec(v, fc_cv, fc_cstate, fc_cstate);
	NOERR();

	/* 关闭新的开放子颜色以确保缓存条目是自包含的 */
	okcolors(v->nfa, v->cm);
	NOERR();

	/* 成功！保存缓存指针 */
	v->wordchrs = fc_cstate;
}

/*
 * processlacon - 生成 LACON 的 NFA 表示
 *
 * 在一般情况下，这只是 newlacon() + newarc()，但某些情况下
 * 可以进行优化。
 */
static void processlacon(struct vars *v,
			 struct state *fc_begin,	/* 解析的 LACON 子于开头 */
			 struct state *fc_end, /* 解析的 LACON 子于结尾 */
			 int fc_latype,
			 struct state *fc_lp,	/* 挂载的左状态 */
			 struct state *fc_rp)	/* 挂载的右状态 */
{
	struct state *fc_s1;
	int			fc_n;

	/*
	 * 检查由单个普通颜色弧（或弧集）组成的环视正则表达式；
	 * 这通常是一个简单的字符或括号表达式。
	 */
	fc_s1 = single_color_transition(fc_begin, fc_end);
	switch (fc_latype)
	{
		case LATYPE_AHEAD_POS:
			/* 如果前瞻正则表达式仅为颜色集 C，则转换为 AHEAD(C) */
			if (fc_s1 != NULL)
			{
				cloneouts(v->nfa, fc_s1, fc_lp, fc_rp, AHEAD);
				return;
			}
			break;
		case LATYPE_AHEAD_NEG:
			/* 如果前瞻正则表达式仅为颜色集 C，则转换为 AHEAD(^C)|$ */
			if (fc_s1 != NULL)
			{
				colorcomplement(v->nfa, v->cm, AHEAD, fc_s1, fc_lp, fc_rp);
				newarc(v->nfa, '$', 1, fc_lp, fc_rp);
				newarc(v->nfa, '$', 0, fc_lp, fc_rp);
				return;
			}
			break;
		case LATYPE_BEHIND_POS:
			/* 如果后顾正则表达式仅为颜色集 C，则转换为 BEHIND(C) */
			if (fc_s1 != NULL)
			{
				cloneouts(v->nfa, fc_s1, fc_lp, fc_rp, BEHIND);
				return;
			}
			break;
		case LATYPE_BEHIND_NEG:
			/* 如果后顾正则表达式仅为颜色集 C，则转换为 BEHIND(^C)|^ */
			if (fc_s1 != NULL)
			{
				colorcomplement(v->nfa, v->cm, BEHIND, fc_s1, fc_lp, fc_rp);
				newarc(v->nfa, '^', 1, fc_lp, fc_rp);
				newarc(v->nfa, '^', 0, fc_lp, fc_rp);
				return;
			}
			break;
		default:
			assert(NOTREACHED);
	}

	/* General case: we need a LACON 子树和弧 */
	fc_n = newlacon(v, fc_begin, fc_end, fc_latype);
	newarc(v->nfa, LACON, fc_n, fc_lp, fc_rp);
}

/*
 * subre - 分配一个 subre
 */
static struct subre * subre(struct vars *v,
	  int fc_op,
	  int fc_flags,
	  struct state *fc_begin,
	  struct state *fc_end)
{
	struct subre *fc_ret = v->treefree;

	/*
	 * 在这里检查堆栈溢出足以保护 parse() 和
	 * 其递归子例程。
	 */
	if (STACK_TOO_DEEP(v->re))
	{
		ERR(REG_ETOOBIG);
		return NULL;
	}

	if (fc_ret != NULL)
		v->treefree = fc_ret->child;
	else
	{
		fc_ret = (struct subre *) MALLOC(sizeof(struct subre));
		if (fc_ret == NULL)
		{
			ERR(REG_ESPACE);
			return NULL;
		}
		fc_ret->chain = v->treechain;
		v->treechain = fc_ret;
	}

	assert(strchr("=b|.*(", fc_op) != NULL);

	fc_ret->op = fc_op;
	fc_ret->flags = fc_flags;
	fc_ret->latype = (char) -1;
	fc_ret->id = 0;				/* 以后将被赋值 */
	fc_ret->capno = 0;
	fc_ret->backno = 0;
	fc_ret->min = fc_ret->max = 1;
	fc_ret->child = NULL;
	fc_ret->sibling = NULL;
	fc_ret->begin = fc_begin;
	fc_ret->end = fc_end;
	ZAPCNFA(fc_ret->cnfa);

	return fc_ret;
}

/*
 * freesubre - 释放一个 subRE 子树
 *
 * 这也释放给定 subRE 的子节点，但不释放其兄弟节点。
 */
static void freesubre(struct vars *v,		/* 可能为 NULL */
		  struct subre *fc_sr)
{
	if (fc_sr == NULL)
		return;

	if (fc_sr->child != NULL)
		freesubreandsiblings(v, fc_sr->child);

	freesrnode(v, fc_sr);
}

/*
 * freesubreandsiblings - 释放一个 subRE 子树
 *
 * 这也释放给定 subRE 的子节点，以及任何后续的兄弟节点。
 */
static void freesubreandsiblings(struct vars *v,	/* 可能为 NULL */
					 struct subre *fc_sr)
{
	while (fc_sr != NULL)
	{
		struct subre *fc_next = fc_sr->sibling;

		freesubre(v, fc_sr);
		fc_sr = fc_next;
	}
}

/*
 * freesrnode - 释放 subRE 子树中的一个节点
 */
static void freesrnode(struct vars *v,		/* 可能为 NULL */
		   struct subre *fc_sr)
{
	if (fc_sr == NULL)
		return;

	if (!NULLCNFA(fc_sr->cnfa))
		freecnfa(&fc_sr->cnfa);
	fc_sr->flags = 0;				/* 特别是，不能在使用中 */
	fc_sr->child = fc_sr->sibling = NULL;
	fc_sr->begin = fc_sr->end = NULL;

	if (v != NULL && v->treechain != NULL)
	{
		/* 我们仍在解析，也许可以重用 subre */
		fc_sr->child = v->treefree;
		v->treefree = fc_sr;
	}
	else
		FREE(fc_sr);
}

/*
 * removecaptures - 移除不必要的捕获 subRE
 *
 * 如果调用者说它不关心子表达式匹配数据，
 * 我们可以删除未被任何回溯引用的 subRE 上的“捕获”标记，
 * 然后简化任何变得不复杂的内容。
 * 仅在设置 REG_NOSUB 标志时调用此函数。
 */
static void removecaptures(struct vars *v,
			   struct subre *fc_t)
{
	struct subre *fc_t2;

	assert(fc_t != NULL);

	/*
	 * 如果这不是一个回溯引用目标，清除 capno 并暂时
	 * 清除 CAP 标志。
	 */
	if (!(fc_t->flags & BRUSE))
	{
		fc_t->capno = 0;
		fc_t->flags &= ~CAP;
	}

	/* 现在递归到子节点 */
	for (fc_t2 = fc_t->child; fc_t2 != NULL; fc_t2 = fc_t2->sibling)
	{
		removecaptures(v, fc_t2);
		/* 如果子节点的 CAP 标志仍然设置，则向上传播 CAP 标志 */
		if (fc_t2->flags & CAP)
			fc_t->flags |= CAP;
	}

	/*
	 * 如果 t 现在既不包含捕获也不包含回溯引用，则不再需要关注
	 * 其子匹配边界，因此我们可以将其简化为一个简单的 DFA 节点。
	 * （特别注意 MIXED 子节点的贪婪性在这里不是障碍，
	 * 所以我们不使用 MESSY() 宏。）
	 */
	if ((fc_t->flags & (CAP | BACKR)) == 0)
	{
		if (fc_t->child)
			freesubreandsiblings(v, fc_t->child);
		fc_t->child = NULL;
		fc_t->op = '=';
		fc_t->flags &= ~MIXED;
	}
}

/*
 * numst - 计数树节点（分配“id”索引）
 */
static int						/* 下一个数字 */
numst(struct subre *fc_t,
	  int fc_start)				/* 子树数字的起始点 */
{
	int			fc_i;
	struct subre *fc_t2;

	assert(fc_t != NULL);

	fc_i = fc_start;
	fc_t->id = fc_i++;
	for (fc_t2 = fc_t->child; fc_t2 != NULL; fc_t2 = fc_t2->sibling)
		fc_i = numst(fc_t2, fc_i);
	return fc_i;
}

/*
 * markst - 将树节点标记为 INUSE
 *
 * 注意：这比看起来要微妙得多。 在初始
 * 解析正则表达式时，所有 subres 都链接到 treechain 列表中；
 * 被丢弃的也被链接到 treefree 列表中以便可能重用。
 * 在我们完成创建正则表达式所需的所有 subres 后，运行 markst()
 * 然后 cleanst()，这将导致丢弃所有从 v->tree 无法到达的 subres。
 * 然后我们清除 v->treechain，表明必须通过从 v->tree 向下查找来找到 subres。
 * 这改变了 freesubre() 的行为：它将从今往后 FREE() 不需要的 subres，
 * 而不是将它们放入 treefree 列表中。 
 * （如果早些这样做，将导致 treechain 列表中的悬空链接。）
 * 这意味着 freev() 在标记和清理完成后调用时将正确清理；
 * 但如果在这个状态转换的中途调用，就会失效，因此我们不能在
 * 这两个函数之间出错。
 */
static void markst(struct subre *fc_t)
{
	struct subre *fc_t2;

	assert(fc_t != NULL);

	fc_t->flags |= INUSE;
	for (fc_t2 = fc_t->child; fc_t2 != NULL; fc_t2 = fc_t2->sibling)
		markst(fc_t2);
}

/*
 * cleanst - 释放任何未标记为 INUSE 的树节点
 */
static void cleanst(struct vars *v)
{
	struct subre *fc_t;
	struct subre *fc_next;

	for (fc_t = v->treechain; fc_t != NULL; fc_t = fc_next)
	{
		fc_next = fc_t->chain;
		if (!(fc_t->flags & INUSE))
			FREE(fc_t);
	}
	v->treechain = NULL;
	v->treefree = NULL;			/* 只是出于一般原则 */
}

/*
 * nfatree - 将一个 subRE 子树转化为紧凑的 NFA 树
 */
static long						/* 优化来自顶节点的结果 */
nfatree(struct vars *v,
		struct subre *fc_t,
		FILE *fc_f)				/* 用于调试输出 */
{
	struct subre *fc_t2;

	assert(fc_t != NULL && fc_t->begin != NULL);

	for (fc_t2 = fc_t->child; fc_t2 != NULL; fc_t2 = fc_t2->sibling)
		(DISCARD) nfatree(v, fc_t2, fc_f);

	return nfanode(v, fc_t, 0, fc_f);
}

/*
 * nfanode - 为 nfatree 或 lacons 创建一个 NFA
 *
 * 如果 converttosearch 为真，向 NFA 应用 makesearch()。
 */
static long						/* 优化结果 */
nfanode(struct vars *v,
		struct subre *fc_t,
		int fc_converttosearch,
		FILE *fc_f)				/* 用于调试输出 */
{
	struct nfa *fc_nfa;
	long		fc_ret = 0;

	assert(fc_t->begin != NULL);

#ifdef REG_DEBUG
	if (fc_f != NULL)
	{
		char		fc_idbuf[50];

		fprintf(fc_f, "\n\n\n========= TREE NODE %s ==========\n",
				stid(fc_t, fc_idbuf, sizeof(fc_idbuf)));
	}
#endif
	fc_nfa = newnfa(v, v->cm, v->nfa);
	NOERRZ();
	dupnfa(fc_nfa, fc_t->begin, fc_t->end, fc_nfa->init, fc_nfa->final);
	fc_nfa->flags = v->nfa->flags;
	if (!ISERR())
		specialcolors(fc_nfa);
	if (!ISERR())
		fc_ret = optimize(fc_nfa, fc_f);
	if (fc_converttosearch && !ISERR())
		makesearch(v, fc_nfa);
	if (!ISERR())
		compact(fc_nfa, &fc_t->cnfa);

	freenfa(fc_nfa);
	return fc_ret;
}

/*
 * newlacon - 分配一个前瞻约束 subRE
 */
static int						/* lacon 编号 */
newlacon(struct vars *v,
		 struct state *fc_begin,
		 struct state *fc_end,
		 int fc_latype)
{
	int			fc_n;
	struct subre *fc_newlacons;
	struct subre *fc_sub;

	if (v->nlacons == 0)
	{
		fc_n = 1;					/* skip 0th */
		fc_newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre));
	}
	else
	{
		fc_n = v->nlacons;
		fc_newlacons = (struct subre *) REALLOC(v->lacons,
											 (fc_n + 1) * sizeof(struct subre));
	}
	if (fc_newlacons == NULL)
	{
		ERR(REG_ESPACE);
		return 0;
	}
	v->lacons = fc_newlacons;
	v->nlacons = fc_n + 1;
	fc_sub = &v->lacons[fc_n];
	fc_sub->begin = fc_begin;
	fc_sub->end = fc_end;
	fc_sub->latype = fc_latype;
	ZAPCNFA(fc_sub->cnfa);
	return fc_n;
}

/*
 * freelacons - 释放前瞻约束 subRE 向量
 */
static void freelacons(struct subre *fc_subs,
		   int fc_n)
{
	struct subre *fc_sub;
	int			fc_i;

	assert(fc_n > 0);
	for (fc_sub = fc_subs + 1, fc_i = fc_n - 1; fc_i > 0; fc_sub++, fc_i--)	/* no 0th */
		if (!NULLCNFA(fc_sub->cnfa))
			freecnfa(&fc_sub->cnfa);
	FREE(fc_subs);
}

/*
 * rfree - 释放整个 RE (regfree 的内部部分)
 */
static void rfree(regex_t *fc_re)
{
	struct guts *fc_g;

	if (fc_re == NULL || fc_re->re_magic != REMAGIC)
		return;

	fc_re->re_magic = 0;			/* 使 RE 无效 */
	fc_g = (struct guts *) fc_re->re_guts;
	fc_re->re_guts = NULL;
	fc_re->re_fns = NULL;
	if (fc_g != NULL)
	{
		fc_g->magic = 0;
		freecm(&fc_g->cmap);
		if (fc_g->tree != NULL)
			freesubre((struct vars *) NULL, fc_g->tree);
		if (fc_g->lacons != NULL)
			freelacons(fc_g->lacons, fc_g->nlacons);
		if (!NULLCNFA(fc_g->search))
			freecnfa(&fc_g->search);
		FREE(fc_g);
	}
}

/* 
 * rcancelrequested - 检查是否有外部请求取消正则表达式操作
 *
 * 返回非零以错误代码 REG_CANCEL 失败该操作，
 * 返回零以继续进行
 *
 * 当前实现是 Postgres 特定的。如果我们能分割正则表达式代码为独立库，
 * 将需要一些 API 让应用程序定义回调函数。
 */
static int rcancelrequested(void)
{
	return InterruptPending && (QueryCancelPending || ProcDiePending);
}

/* 
 * rstacktoodeep - 检查栈是否危险地深
 *
 * 返回非零以错误代码 REG_ETOOBIG 失败该操作，
 * 返回零以继续进行
 *
 * 当前实现是 Postgres 特定的。如果我们能分割正则表达式代码为独立库，
 * 将需要一些 API 让应用程序定义回调函数。
 */
static int rstacktoodeep(void)
{
	return stack_is_too_deep();
}

#ifdef REG_DEBUG

/* 
 * dump - 以人类可读的形式转储一个 RE
 */
static void dump(regex_t *fc_re,
	 FILE *fc_f)
{
	struct guts *fc_g;
	int			fc_i;

	if (fc_re->re_magic != REMAGIC)
		fprintf(fc_f, "bad magic number (0x%x not 0x%x)\n", fc_re->re_magic,
				REMAGIC);
	if (fc_re->re_guts == NULL)
	{
		fprintf(fc_f, "NULL guts!!!\n");
		return;
	}
	fc_g = (struct guts *) fc_re->re_guts;
	if (fc_g->magic != GUTSMAGIC)
		fprintf(fc_f, "bad guts magic number (0x%x not 0x%x)\n", fc_g->magic,
				GUTSMAGIC);

	fprintf(fc_f, "\n\n\n========= DUMP ==========\n");
	fprintf(fc_f, "nsub %d, info 0%lo, csize %d, ntree %d\n",
			(int) fc_re->re_nsub, fc_re->re_info, fc_re->re_csize, fc_g->ntree);

	dumpcolors(&fc_g->cmap, fc_f);
	if (!NULLCNFA(fc_g->search))
	{
		fprintf(fc_f, "\nsearch:\n");
		dumpcnfa(&fc_g->search, fc_f);
	}
	for (fc_i = 1; fc_i < fc_g->nlacons; fc_i++)
	{
		struct subre *fc_lasub = &fc_g->lacons[fc_i];
		const char *fc_latype;

		switch (fc_lasub->latype)
		{
			case LATYPE_AHEAD_POS:
				fc_latype = "positive lookahead";
				break;
			case LATYPE_AHEAD_NEG:
				fc_latype = "negative lookahead";
				break;
			case LATYPE_BEHIND_POS:
				fc_latype = "positive lookbehind";
				break;
			case LATYPE_BEHIND_NEG:
				fc_latype = "negative lookbehind";
				break;
			default:
				fc_latype = "???";
				break;
		}
		fprintf(fc_f, "\nla%d (%s):\n", fc_i, fc_latype);
		dumpcnfa(&fc_lasub->cnfa, fc_f);
	}
	fprintf(fc_f, "\n");
	dumpst(fc_g->tree, fc_f, 0);
}

/* 
 * dumpst - 转储一个子 RE 树
 */
static void dumpst(struct subre *fc_t,
	   FILE *fc_f,
	   int fc_nfapresent)			/* 原始 NFA 还在吗？ */
{
	if (fc_t == NULL)
		fprintf(fc_f, "null tree\n");
	else
		stdump(fc_t, fc_f, fc_nfapresent);
	fflush(fc_f);
}

/* 
 * stdump - dumpst 的递归实质
 */
static void stdump(struct subre *fc_t,
	   FILE *fc_f,
	   int fc_nfapresent)			/* 原始 NFA 还在吗？ */
{
	char		fc_idbuf[50];
	struct subre *fc_t2;

	fprintf(fc_f, "%s. `%c'", stid(fc_t, fc_idbuf, sizeof(fc_idbuf)), fc_t->op);
	if (fc_t->flags & LONGER)
		fprintf(fc_f, " longest");
	if (fc_t->flags & SHORTER)
		fprintf(fc_f, " shortest");
	if (fc_t->flags & MIXED)
		fprintf(fc_f, " hasmixed");
	if (fc_t->flags & CAP)
		fprintf(fc_f, " hascapture");
	if (fc_t->flags & BACKR)
		fprintf(fc_f, " hasbackref");
	if (fc_t->flags & BRUSE)
		fprintf(fc_f, " isreferenced");
	if (!(fc_t->flags & INUSE))
		fprintf(fc_f, " UNUSED");
	if (fc_t->latype != (char) -1)
		fprintf(fc_f, " latype(%d)", fc_t->latype);
	if (fc_t->capno != 0)
		fprintf(fc_f, " capture(%d)", fc_t->capno);
	if (fc_t->backno != 0)
		fprintf(fc_f, " backref(%d)", fc_t->backno);
	if (fc_t->min != 1 || fc_t->max != 1)
	{
		fprintf(fc_f, " {%d,", fc_t->min);
		if (fc_t->max != DUPINF)
			fprintf(fc_f, "%d", fc_t->max);
		fprintf(fc_f, "}");
	}
	if (fc_nfapresent)
		fprintf(fc_f, " %ld-%ld", (long) fc_t->begin->no, (long) fc_t->end->no);
	if (fc_t->child != NULL)
		fprintf(fc_f, " C:%s", stid(fc_t->child, fc_idbuf, sizeof(fc_idbuf)));
	/* 打印第二个子节点不是必要的，但通常是有帮助的 */
	if (fc_t->child != NULL && fc_t->child->sibling != NULL)
		fprintf(fc_f, " C2:%s", stid(fc_t->child->sibling, fc_idbuf, sizeof(fc_idbuf)));
	if (fc_t->sibling != NULL)
		fprintf(fc_f, " S:%s", stid(fc_t->sibling, fc_idbuf, sizeof(fc_idbuf)));
	if (!NULLCNFA(fc_t->cnfa))
	{
		fprintf(fc_f, "\n");
		dumpcnfa(&fc_t->cnfa, fc_f);
	}
	fprintf(fc_f, "\n");
	for (fc_t2 = fc_t->child; fc_t2 != NULL; fc_t2 = fc_t2->sibling)
		stdump(fc_t2, fc_f, fc_nfapresent);
}

/* 
 * stid - 识别用于转储的子树节点
 */
static const char *				/* 指向 buf 或常量字符串 */
stid(struct subre *fc_t,
	 char *fc_buf,
	 size_t fc_bufsize)
{
	/* 足够大以容纳十六进制整数或十进制 t->id？ */
	if (fc_bufsize < sizeof(void *) * 2 + 3 || fc_bufsize < sizeof(fc_t->id) * 3 + 1)
		return "unable";
	if (fc_t->id != 0)
		sprintf(fc_buf, "%d", fc_t->id);
	else
		sprintf(fc_buf, "%p", fc_t);
	return fc_buf;
}
#endif							/* REG_DEBUG */


#include "regc_lex.c"
#include "regc_color.c"
#include "regc_nfa.c"
#include "regc_cvec.c"
#include "regc_pg_locale.c"
#include "regc_locale.c"
